package 数据结构.栈和队列.Algorithm;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/*题目：150 求逆波兰的值
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

        请你计算该表达式。返回一个表示表达式值的整数。

        注意：

        有效的算符为 '+'、'-'、'*' 和 '/' 。
        每个操作数（运算对象）都可以是一个整数或者另一个表达式。
        两个整数之间的除法总是 向零截断 。
        表达式中不含除零运算。
        输入是一个根据逆波兰表示法表示的算术表达式。
        答案及所有中间计算结果可以用 32 位 整数表示。*/
public class evalRPN {
    public static void main(String[] args) {

    }
    //tokens = ["2","1","+","3","*"]
    //当传进来是数字时，则进栈，当是符号时，则利用栈顶去做计算，注意：是下面那个 符号 栈顶
    public int evalRPN(String[] tokens) {

        Deque<Integer> deque=new ArrayDeque();
        //依次取得元素
        for (int i = 0; i < tokens.length; i++) {
            String a=tokens[i];
            if(!isNumber(a)){
                //代表着不是数字，取栈顶两个进行计算
                //最上面那个
                int pop1 = (int) deque.pop();
                //第二个
                int pop2= (int) deque.pop();
                int sum=0;
                if(a.equals("+")){
                    sum=pop2+pop1;
                }else if(a.equals("-")){
                    sum=pop2-pop1;
                }else if(a.equals("*")){
                    sum=pop2*pop1;
                }else if(a.equals("/")){
                    sum=pop2/pop1;
                }
                //将结果重新放进栈中
                deque.push(sum);
            }else {
                int num=Integer.parseInt(a);
                //代表是数字，进行进栈
                deque.push(num);
            }
        }
        return deque.peek();
    }
    public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
}
